#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int memo[31];
    int fib(int n) {
        memset(memo, -1, sizeof memo);
        int ret = dfs(n);
        return ret;
    }
    int dfs(int n)
    {
        if (memo[n] != -1)
        {
            return memo[n];
        }
        if (n == 0 || n == 1)
        {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
};